package com.computer.fundamentals.algorithm.sort;

import com.computer.util.Constant;
import com.computer.util.UniversalMethod;

public class MergeSort {

    public int[] template;

    /**
     * 初始化并排序
     */
    public int[] initAndSorted(int[] nums) {
        template = new int[nums.length];
        mergeSort(nums, 0, nums.length-1);
        return template;
    }

    /**
     * 归并排序
     */
    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        int i = left, j = mid+1; // i为左半数组的指针，j为右半数组的指针
        int k = 0; // k 表示template数组的指针
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                template[k++] = nums[i++];
            }else {
                template[k++] = nums[j++];
            }
        }

        // 边界处理
        while (i <= mid) {
            template[k++] = nums[i++];
        }
        while (j <= right) {
            template[k++] = nums[j++];
        }

        // 将归并后的子组结果合入nums原数组
        for (int n = 0;n < right - left + 1;n++) {
            nums[n+left] = template[n];
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();

        System.out.println("---------------原数组---------------");
        int[] array = UniversalMethod.createArray(Constant.DEFAULT_ARRAY_LENGTH);
        UniversalMethod.printArray(array);
        System.out.println("\n");

        System.out.println("---------------排序数组---------------");
        int[] sortedArray = mergeSort.initAndSorted(array);
        UniversalMethod.printArray(sortedArray);

    }
}